package LeetCode.Medium;

/*
一个m * n的二维数组中，行数据递增，列数据递增，判断一个数是否存在于这个二维数组中
要求：时间复杂度尽可能的低
解法：从第一行最后一列开始往回查找
        target大于数组当前值，往下搜索
        target小于数组当前值，往前搜索
        target等于数组当前值，返回true
     搜索完毕未找到，返回false
 */
public class Question001 {
    public static void main(String[] args) {
        int[][] matrix = new int[][]{{1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}};
        System.out.println(new Question001().findNumberIn2DArray(matrix, 20));
    }
    public boolean findNumberIn2DArray(int[][] matrix, int target){
        int rows = matrix.length;
        int columns = matrix[0].length;
        int row = 0;
        int column = columns - 1;
        while(row < rows && column < columns){
            if(matrix[row][column] == target){
                return true;
            }else if(matrix[row][column] < target){
                row++;
            }else{
                column--;
            }
        }
        return false;
    }
}
